package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         99,
		Discription: "随机交换二叉搜索树的两个节点后，恢复二叉搜索树",
		Level:       2,
		Labels: map[string]int{
			"栈":     1,
			"二叉树":   1,
			"二叉搜索树": 1,
		},
	})
}

//	中序遍历二叉搜索树，找第一个a[i]>a[i+1]和第二个a[j]>a[j+1]，并将a[i]和a[j+1]互换值（也只可能有一个反序的位置）
//
//  前面更大的换后面更小的
func RecoverTree(root *ds.TreeNode) {
	s := make([]*ds.TreeNode, 0)
	var lastVisited, node1, node2 *ds.TreeNode
	cur := root
	//注意两个条件
	for len(s) > 0 || cur != nil {
		for cur != nil {
			s = append(s, cur)
			cur = cur.Left
		}

		top := s[len(s)-1]
		s = s[:len(s)-1]
		if lastVisited != nil && top.Val < lastVisited.Val {
			node1 = top
			if node2 == nil {
				//如果是第一个反序的位置，将node2置为a[i]，node1置为a[i+1]（因为node2是不会变的，即使后面遇到第二个反序额度位置）
				node2 = lastVisited
			} else {
				break
			}
		}

		lastVisited = top
		cur = top.Right
	}

	node1.Val, node2.Val = node2.Val, node1.Val
}
